#include "../tools.h"

// 需要移除区间的最小数量，就是剩下的区间最多
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int size = intervals.size();
        if(size <= 1) return 0;

        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
            return a[1] != b[1] ? a[1] < b[1] : a[0] < b[0];
        });
        // show(intervals);

        int ndrop = 0;
        int left = 0, right = 1;
        while(right < size){
            if(intervals[right][0] < intervals[left][1]){
                ++ndrop;
                ++right;
            }
            else{
                left = right;
                ++right;
            }
        }

        return ndrop;
    }
};



int main(int argc, char const *argv[])
{
    Solution sol;

    // vector<vector<int>> intervals = {{1,2}, {2,3}, {3,4}, {1,3}};
    vector<vector<int>> intervals = {{1,2}, {1,2}, {1,2}};
    // vector<vector<int>> intervals = {{1,2}, {2,3}};


    int res = sol.eraseOverlapIntervals(intervals);
    cout << res << endl;

    return 0;
}
